package interview;

import java.util.*;

public class lc42_rain {
    public static void main(String[] args) {
        System.out.println(trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
        System.out.println(trap(new int[]{4,2,0,3,2,5}));
    }
    public static int trap(int[] height) {
        //接雨水使用单调栈
        int n = height.length;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        //雨水总量
        int sum = 0;
        for (int i = 1; i < n; i++) {
            //如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，
            // 因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。
            if(!stack.isEmpty() && height[i] < height[stack.peek()])
                stack.push(i);
            //如果相等，需要将下标替换（因为计算宽度用的下标，不替换就会重复计算或者错误计算）
            if(!stack.isEmpty() && height[i] == height[stack.peek()]){
                stack.pop();
                stack.push(i);
            }
            //如果当前元素小于栈顶元素，说明有可能出现凹槽，需要判断
            while(!stack.isEmpty() && height[i] > height[stack.peek()]){
                //栈顶元素就是凹槽的底部，也就是中间位置
                int mid = stack.pop();
                //由于单调递增，所以栈顶的下一个（如果有的话）一定大于栈顶
                if(!stack.isEmpty()){
                    int left = stack.peek();
                    sum += (i - left - 1) * (Math.min(height[i], height[left]) - height[mid]);
                }
            }
            //推出循环证明当前元素小于栈顶元素小于入栈
            stack.push(i);
        }
        return sum;
    }
}
